2^2005 mod 2005 等于多少

1、费马定理：
a是不能被质数p整除的正整数，则有a^p-1 ≡ 1 mod p

则 2^400 ≡ 1 mod 401

又知 2^400 ≡ 1 mod 5
(因为 2^20 mod 5
<=> (2^10)^2 mod 5
<=> (1024)^2 mod 5
<=> 4^2 mod 5
<=> 16 mod 5 ≡ 1 )

所以 2^400 ≡ 1 mod 2005

所以 2^2005 (mod 2005)
<=> 2^5 * (2^400)^5 (mod 2005)
<=> 2^5 (mod 2005)
<=> 32 (mod 2005) ≡ 32

2、

欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数的个数，记做：φ(n)，其中φ(1)被定义为1，但是并没有任何实质的意义。

显然，对于素数p，φ(p)= p -1.对于两个素数p、q，他们的乘积n = pq 满足φ(n) =(p-1)(q-1)

欧拉定理:对于互质的整数a和n，有a^φ(n) ≡ 1 mod n
(以上我就不证明了哈～)

2005 = 5 * 401 (5与401都是质数，且2与2005互质)

φ(2005) =(5-1)(401-1) = 4 * 400 = 1600

所以2^1600 (mod 2005) ≡ 1

2^2005 (mod 2005)
<=> 2^1600 * 2^405 (mod 2005)
<=> 2^405 (mod 2005)
<=> 2^9 * 2^396 (mod 2005)
<=> 2^9 * (2^11)^36 (mod 2005)
<=> 2^9 * (2048)^36 (